/*
 * Poblacion.java
 *
 * Created on 21-nov-2007, 17:46:06
 *
 */

package ia;

import java.util.Iterator;
import java.util.Random;
import java.util.Vector;

/**
 * En esta clase se mantiene la poblacion de soluciones con los operadores de
 * seleccion y cruce.
 * @author Arturo Ferreira
 * @author Manuel Avalos
 */
public class Poblacion {

/**	poblacion Actual */
	public Individuo[] PA;
	
    //Poblacion No Dominada
    public Vector PnD = new Vector();
    //Representa la cantidad de individuos que hay en la poblacion actual.
    private int cantidadActual;
    /**	Vector de Frentes Paretos, o niveles de dominancia */
    public Vector FP = new Vector();
    
    /**	Variables utilizadas para guardas los dos menores fitness de la poblacion */
    private double fitness_1;
    private double fitness_2;
    private int seca_1;//Se guardan los indices donde se encuentrar los individuos
    private int seca_2;
    
    /**	Variables utilizadas para guardar el punto minimo y el punto maximo en un frente pareto dado */
    private double mayor_x = 0;//Para encontrar el punto minimo en el FP
    private double mayor_y = 0;//Para encontrar el punto maximo en el frente Pareto
    private int Minimo_FP;//Para guardar el indice donde se encuentra el punto  minimo del FP
    private int Maximo_FP;//Para guardar el indice donde se encuentra el punto maximo del FP
    
    
    /**	Constantes que definen las probabilidades de cruce y mutacion */
    public static final double pm = 0.01;
    public static final double pc = 0.6;
    /**Distancia  definida para el radio del nicho*/
    private double frontera_nicho;
    
    //Para realizar el clustering.
    private int maxTamanhoPnD = 100;//Tamanho maximo de la poblacion de no dominados.
    private int [] clusters;//Contiene los individuos divididos en clusters.
    private int [] listSgteClusters;
    private int numClusters = 0;
    
    public Poblacion() {
    }
    /**
    *
    * Metodo utilizado para seleccionar los padres para realizar el cruce. Se realiza un torneo
    * binario, descritoo en Apuntes de Coello, Capitulo 6 (Pag. 126).
    * @return El individuo seleccionado.
    *
    */
    public Individuo Seleccionar() {

        Random r = new Random();
        int individuo1;
        int individuo2;
        int padre;
        int sorteo;
        int limite = this.PA.length;
        individuo1 = r.nextInt(limite);
        individuo2 = r.nextInt(limite);
        while (individuo1 == individuo2) {
            individuo2 = r.nextInt(limite);
        }
        Individuo opcion1 = this.PA[individuo1];
        Individuo opcion2 = this.PA[individuo2];
        if (opcion1.getFitness() > opcion2.getFitness()) {
            padre = individuo1;
        } else if (opcion1.getFitness() < opcion2.getFitness()) {
            padre = individuo2;
        } else {
            sorteo = r.nextInt(2);
            if (sorteo == 0) {
                padre = individuo1;
            } else {
                padre = individuo2;
            }
        }
        return this.PA[padre];
    }

    /**
     * Asigna el fitness a todos los individuos de la poblacion, por medio del NSGA
     * @return Retorna el frente pareto de la poblacion
     * */
    @SuppressWarnings(value = "unchecked")
    public Vector AsignarFitness_NSGA() {

        Vector frentes = new Vector(); //Vector de frentes
        //df es el valor de fitness que se le da a los individuos del mismo frente
        //El valor inicial de df es el tamanho de la poblacion.
        double df = this.PA.length;
        Vector NoDominados = new Vector();
        Vector Poblacion = new Vector();

        for (int i = 0; i < PA.length; i++) {
            Poblacion.addElement(this.getIndividuo(i));
        }
        while (!Poblacion.isEmpty()) {
            NoDominados = this.BuscarYElminarNoDominados(Poblacion);

            //Asignar a los no dominados el mismo fitness
            for (int i = 0; i < NoDominados.size(); i++) {
                Individuo individuo_i = (Individuo) NoDominados.elementAt(i);
                individuo_i.fitness = df;
            }

            //Hago fitness Sharing a los no dominados, esa funcion devuelve el peor fitness asignado
            df = this.fitness_sharing(NoDominados);

            df = df - df * 0.1; //Se reduce df en exilon para el siguiente grupo de no dominados
            //Guardo los elementos no dominados en el frente actual
            if (!NoDominados.isEmpty()) {
                frentes.addElement(NoDominados.clone());
            }

            NoDominados.clear(); //Inicializo el vector auxiliar para el sgte frente.
            //Marco todos los elementos de la poblacion como no dominados
            for (int i = 0; i < Poblacion.size(); i++) {
                Individuo individuo_i = (Individuo) Poblacion.elementAt(i);
                individuo_i.setDominado(false);
            }
        } //Fin del while
        //Recompongo la poblacion con los elementos de todos los frentes
        for (int i = 0; i < frentes.size(); i++) {
            Poblacion.addAll((Vector) frentes.elementAt(i));
        }

        this.fitness_1 = this.PA.length;
        this.fitness_2 = this.PA.length;
        //Inserto en vec_poblacion la poblacion con su nuevo fitness.
        for (int i = 0; i < Poblacion.size(); i++) 
        {
            this.PA[i] = (Individuo) Poblacion.elementAt(i);

            //Eligo los dos individuos con menor fitness
            if (this.fitness_1 > this.PA[i].fitness) 
            {
                this.seca_1 = i;
                this.fitness_1 = this.PA[i].fitness;
            } 
            else if (this.fitness_2 > this.PA[i].fitness)
            {
                this.seca_2 = i;
                this.fitness_2 = this.PA[i].fitness;
            }
            
        }


        return (Vector) frentes.elementAt(0);
    }

    /**
     * Implementa el procedimiento de fitness Sharing, compartiendo el fitness 
     * entre los individuos del frente actual pasado como parametro.
     * @param frente_actual Es la poblacion a la que se le aplicara fitness Sharing
     * @return Retorna el menor fitness que tiene un individuo de esa poblacion.
     * */
    
    private double fitness_sharing(Vector frente_actual) {
        double dist = 0; //distancia entre los individuos
        double valor_sharing;

        double menor_fitness = this.PA.length; //Inicialmente tiene que ser un numero grande
        Individuo a = (Individuo) frente_actual.elementAt(this.Minimo_FP);
        Individuo b = (Individuo) frente_actual.elementAt(this.Maximo_FP);
        this.frontera_nicho = a.distancia(b) * 0.1;
        

        for (int i = 0; i < frente_actual.size(); i++) {
            valor_sharing = 0;
            Individuo individuo_i = (Individuo) frente_actual.elementAt(i);
            for (int j = 0; j < frente_actual.size(); j++) {

                Individuo individuo_j = (Individuo) frente_actual.elementAt(j);
                dist = individuo_j.distancia(individuo_i);
                if (dist <= this.frontera_nicho) {
                    valor_sharing = 1 - Math.pow(dist / this.frontera_nicho, 2);
                } else {
                    valor_sharing = 0;
                }
                individuo_i.ncount = individuo_i.ncount + valor_sharing;
            }
            individuo_i.fitness = individuo_i.fitness / individuo_i.ncount;
            individuo_i.ncount=0;//inicializo el contador. Por que este cambia por cada grupo de no dominados
            if (menor_fitness > individuo_i.fitness) {
                menor_fitness = individuo_i.fitness;
            }
            
        }

        this.Minimo_FP = 0;
        this.Maximo_FP = 0;
        this.mayor_x = 0;
        this.mayor_y = 0;
        return menor_fitness;
    }
    /**
    *
    * Metodo utilizado para calcular los valores del vector objetivo de cada individuo de la poblacion actual.
    * @param matrices Contiene la matriz de distancia y matrices de flujos utilizados para el calculo.
    *
    */
    public void calcularValorObjetivo(double[][] matrizVarianza, double [] vectorRendimiento) {
        for (int i = 0; i < this.PA.length; i++) {
            this.PA[i].calcularValorObjetivo(matrizVarianza, vectorRendimiento);
        }
    }

    /**
    *
    * Metodo utilizado para crear la primera poblacion, al iniciar la corrida del algoritmo.Los
    * cromosomas de los son generados aleatoriamente y hacemos cumplir la restriccion de que
     * la suma de los alelos sea igual a 1.
    * @param nroIndv Cantidad de individuos que debe tener la poblacion.
    * @param cantAcciones, viene a ser las cantidad de acciones con que se trabajara. Define el
    * tamaño del cromosoma.
    *
    */
    public void GenerarPoblacion(int nroIndv, int cantAcciones) {
        this.PA = new Individuo[nroIndv];
        double[] aux = new double[cantAcciones];//cromosoma auxiliar
        Random r = new Random();
        
              
          // Se utiliza un random de modo a generar individuos diferentes. Controlando
         //que todos los numeros generados para un individuo sean diferentes.
        this.cantidadActual = nroIndv;
        for (int i = 0; i < nroIndv; i++) {            
            double sumaAlelos=0;
            
            for (int k = 0; k < aux.length; k++) {
                aux[k] = r.nextDouble();
                
            }
            for (int k = 0; k < aux.length; k++) {
                sumaAlelos=sumaAlelos + aux[k];                
            }
            //Hacemos cumplir la restriccion de que la suma de los alelos 
            //de un cromosoma sea igual a 1.
            for (int k = 0; k < aux.length; k++) {
                aux[k]=aux[k]*(1/sumaAlelos);                
            }
            this.PA[i] = new Individuo(aux);
            aux = new double[cantAcciones];
        }
         
    }

    
    /**
    *
    * Este metodo busca y elimina los elementos no dominados de la poblacion pasada como parametro.
    * @param Poblacion Poblacion donde se buscan lo nodominados y se los elimina.
    * @return Un Vector que contiene a los No Dominados
    *
    */
    @SuppressWarnings(value = "unchecked")
    public Vector BuscarYElminarNoDominados(Vector Poblacion) {

        Vector aux = new Vector(); //auxiliar para guardar luego en el vector de frentes
        for (int i = 0; i < Poblacion.size(); i++) {
            Individuo individuo_i = (Individuo) Poblacion.elementAt(i);
            for (int j = 0; j < Poblacion.size(); j++) {

                Individuo individuo_j = (Individuo) Poblacion.elementAt(j);
                if (i != j && individuo_j.DominaA(individuo_i)) {
                    individuo_i.setDominado(true);
                    break;
                }
            }
        }

        //Guardo los elementos no dominados
        for (int i = 0; i < Poblacion.size(); i++)
        {
            Individuo individuo_i = (Individuo) Poblacion.elementAt(i);
            if (!individuo_i.isDominado()) 
            {
                    aux.addElement(individuo_i);
                    //Guardo los indices de los puntos Maximos y Minimos del FP
                    if (mayor_x < individuo_i.getValorObjetivo(0))
                    {
                           mayor_x = individuo_i.getValorObjetivo(0);
                           Minimo_FP = aux.size() - 1;
                    }

                   if (mayor_y < individuo_i.getValorObjetivo(1)) 
                   {
                          Maximo_FP = aux.size() - 1;
                          mayor_y = individuo_i.getValorObjetivo(1);
                   }
           }
      }
        
        // Borro los no dominados.
        int j=0;
        do
        {        
            Individuo individuo_i = (Individuo) Poblacion.elementAt(j);
            if (!individuo_i.isDominado())
            {
               Poblacion.removeElementAt(j);
               j--;
            }
            j++;
        }while(j<Poblacion.size());     
     
        return aux;
    }

    public int getCantidadIndividuos() {
        return this.PA.length;
    }

    public static Vector BuscarNoDominados(Vector Poblacion)
    {
        Vector aux = new Vector(); //auxiliar para guardar luego en el vector de frentes
        for (int i = 0; i < Poblacion.size(); i++) {
            Individuo individuo_i = (Individuo) Poblacion.elementAt(i);
            for (int j = 0; j < Poblacion.size(); j++) {

                Individuo individuo_j = (Individuo) Poblacion.elementAt(j);
                if (i != j && individuo_j.DominaA(individuo_i)) {
                    individuo_i.setDominado(true);
                    break;
                }
            }
        }

        //Guardo los elementos no dominados
        for (int i = 0; i < Poblacion.size(); i++)
        {
            Individuo individuo_i = (Individuo) Poblacion.elementAt(i);
            if (!individuo_i.isDominado()) 
            {
                    aux.addElement(individuo_i);
            }
        }
        
        return aux;
    }
    /**
    *
    * Metodo utilizado para obtener un individuo determinado de la Poblacion Actual.
    * @param i Indice del individuo dentro de la Poblacion Actual.
    * @return El individuo pedido.
    *
    */
    public Individuo getIndividuo(int i) {
        return this.PA[i];
    }

    /**
     * Se reemplazan los peores individuos de la poblacion, por los nuevos individuos
     * */
    public void reemplazar(Individuo[] evolucionados) {

        this.PA[this.seca_1] = evolucionados[0];
        this.PA[this.seca_2] = evolucionados[1];
        
        
    }

    /**
     * Inicializa las variables para encontrar los peores individuos.
     * */
    public void setVariables() {
        this.seca_1 = this.PA.length - 1;
        this.seca_2 = this.PA.length - 1;
        fitness_1=this.PA.length;
        fitness_2=this.PA.length;
    }

    /**
    *
    * Metodo utilizado para realizar el proceso de evolucion: Seleccion, Cruce, Mutacion.
    * @param matrices Son las matrices de flujos y distancia.
    *
    */
    public void seleccionYevolucion_NSGA(double[] rendimientos, double[][]covarianza) 
    {
        Individuo padre1;
        Individuo padre2;
        Random r = new Random();
        Individuo[] NewPoblacion=new Individuo[this.PA.length];//Vector que contendra a la nueva poblacion.
        Individuo[] aux;
        int cantNewPoblacion=0;
        
        //Creamos un nueva poblacion con los hijos, y esa reemplazara completamente a la
        //poblacion de los padres.
        do {
            padre1 = this.Seleccionar();

            do {
                padre2 = this.Seleccionar();
            } while (padre1.igual(padre2));
            
            if (r.nextDouble() <= this.pc) {
                aux = padre1.cruzar(padre2);
                if (r.nextDouble() > this.pm) {
                    aux[0].mutar();

                }
                if (r.nextDouble() <= this.pm) {
                    aux[1].mutar();
                }
                aux[0].calcularValorObjetivo(covarianza, rendimientos);
                aux[1].calcularValorObjetivo(covarianza, rendimientos);
                
                NewPoblacion[cantNewPoblacion]=aux[0];
                cantNewPoblacion++;
                if(cantNewPoblacion < this.PA.length)
                {
                    NewPoblacion[cantNewPoblacion]=aux[1];
                    cantNewPoblacion++;
                }
                

            }
        } while (cantNewPoblacion < this.PA.length);
        
        this.PA=NewPoblacion;
        
    }

    public void InsertaFrentePareto(Vector ND) {

        boolean dominado = false;
        if (FP.isEmpty()) {
            FP.addAll(ND);
        } else {

            for (int j = 0; j < ND.size(); j++) {

                Individuo individuo_j = (Individuo) FP.elementAt(j);
                for (int i = 0; i < FP.size(); i++) {
                    Individuo individuo_i = (Individuo) FP.elementAt(i);
                    if (individuo_i.DominaA(individuo_j)) {
                        dominado = true;
                        break;
                    }
                }
                if (!dominado) {
                    FP.addElement(individuo_j);
                    dominado = false;
                }
            }
        }
    }
    
    ////----------------------METODOS SPEA-----------------------------/////
    
    /**
     *
     * Metodo utilizado para asignar el fitness de todos los individuos, primero a los individuos
     * de la Poblacion de No dominados y luego de la Poblacion Actual.
     *
     */
    public void AsignarFitness_SPEA() {
        int cont = 0;
        //Ciclo para recorrer la Poblacion de No Dominados.
        for (int i = 0; i < this.PnD.size(); i++) {
            //Quitamos un individuo de dicha poblacion.
            Individuo individuo = (Individuo) this.PnD.elementAt(i);
            //Ciclo para recorrer la Poblacion Actual.
            for (int j = 0; j < this.cantidadActual; j++) {
                //Contamos cuantos  individuos en la Poblacion Actual domina el individuo de la
                //Poblacion de No dominados.
                if (individuo.DominaA(this.PA[j])) {
                    cont++;
                }
            }            
            //Guardamos el streng del individuo de la Poblacion de No dominados.
            individuo.setStreng((double) cont / (double) this.cantidadActual);
            //Guardamos el fitness del individuo de la Poblacion de No dominados.
            individuo.setFitness(1 / individuo.getStreng());
            cont = 0;
        }
        //Ciclo para recorrer la Poblacion Actual.
        for (int i = 0; i < this.cantidadActual; i++) {
            //Ciclo para recorrer la Poblacion de No Dominados.
            for (int j = 0; j < this.PnD.size(); j++) {
                //Quitamos un individuo de la Poblacion de No Dominados.
                Individuo individuo = (Individuo) this.PnD.elementAt(j);
                //Al streng del individuo de la Poblacion Actual vamos sumando el streng de todos
                //los individuos de la Poblacion de No Dominados que dominan a este.
                if (individuo.DominaA(this.PA[i])) {
                    this.PA[i].setStreng(individuo.getStreng() + this.PA[i].getStreng());
                }
            }
            //Guardamos el fitness del individuo de la Poblacion Actual.
            this.PA[i].setFitness(1 / this.PA[i].getStreng());
        }
    }
    
    /**
     *
     * Metodo utilizado para borrar los individuos no dominados de la Poblacion Actual.
     * @param indices Contiene los indices de todos los individuos no dominados dentro de la Poblacion Actual.
     *
     */
    public void borrarNoDominados(Vector indices) {
        int indice;
        //Ciclo para recorrer el vector de indices.
        for (int j = 0; j < indices.size(); j++) {
            indice = (Integer) indices.get(j);
            //Eliminamos el individuo no dominado de la Poblacion Actual
            this.PA[indice] = null;
        }
        //Ciclo para recorrer la Poblacion Actual.
        for (int i = 0; i < this.cantidadActual; i++) {
            //Si encontramos un null, lo enviamos hacia el final, del vector de la Poblacion Actual.
            if (this.PA[i] == null) {
                for (int j = i + 1; j < this.cantidadActual; j++) {
                    if (this.PA[j] != null) {
                        this.PA[i] = this.PA[j];
                        this.PA[j] = null;
                        break;
                    }
                }
            }
        }
        //Actualizamos la cantidad de la Poblacion Actual, ya que hemos eliminado algunos individuos.
        this.cantidadActual -= indices.size();
    }
    /**
     *
     * Metodo utilizado para copiar los individuos no dominados de la Poblacion Actual a la
     * Poblacion de No Dominados.
     * @return Los indices de los individuos no dominados dentro de la Poblacion Actual,
     * en un arreglo de tipo Vector.
     *
     */
    public Vector copiarNoDominados() {
        //Creamos un objeto de tipo Vector.
        Vector indicesNoDominados = new Vector();
        //Variable utilizada para saber si un individuo es dominado o no.
        boolean dominado = false;
        //Ciclo utilizado para recorre todos los individuos de la poblacion actual.
        for (int i = 0; i < this.cantidadActual; i++) {
            //Sacamos un individuo de la poblacion.
            Individuo individuo = this.PA[i];
            //Ciclo utilizado para saber si algun individuo de la poblacion domina al individuo que quitamos.
            for (int j = 0; j < this.cantidadActual; j++) {
                if (i != j) {
                    //Sacamos otro individuo de la poblacion.
                    Individuo aux = this.PA[j];
                    //Preguntamos si domina al primer individuo que quitamos.
                    dominado = aux.DominaA(individuo);
                    //Si domina al primer individuo salimos del ciclo en busca de otro individuo.
                    if (dominado) {
                        break;
                    }
                }
            }
            //Si encontramos un no dominado lo agregamos en la Poblacion de No Dominados y guardamos su indice en la Poblacion Actual.
            if (!dominado) {
                this.PnD.add(individuo);
                indicesNoDominados.add(i);
            }
        }
        //Retornamos los indices de los no dominados.
        return indicesNoDominados;
    }
    /**
     *
     * Metodo utilizado para eliminar los individuos que son dominados por los nuevos
     * individuos que forman parte de la Poblacion de No Dominados.
     *
     */
    public void eliminacionEnPnd() {
        //Ciclo para recorrer la Poblacion de No Dominados.
        for (int i = 0; i < this.PnD.size(); i++) {
            //Quitamos un individuo de la poblacion.
            Individuo individuo = (Individuo) this.PnD.elementAt(i);
            //Ciclo para recorrer la Poblacion de No Dominados.
            for (int j = 0; j < this.PnD.size(); j++) {
                if (j != i) {
                    //Quitamos otro individuo de la poblacion.
                    Individuo aux = (Individuo) this.PnD.elementAt(j);
                    //Si encontramos que el primer individuo domina domina al segundo individuo
                    //se elimina al segundo de la Poblacion de No dominados.
                    if (individuo.DominaA(aux)) {
                        this.PnD.removeElementAt(j);
                    }
                }
            }
        }
    }
    
    /**
     *
     * Metodo utilizado para seleccionar los padres para realizar el cruce. Se realiza un torneo
     * binario, descritoo en Apuntes de Coello, Capitulo 6 (Pag. 126).
     * @param poblaciones Contiene los individuos de ambas poblaciones.
     * @return El indice del padre seleccionado dentro de la union de las poblociones.
     *
     */
    public int seleccionarPadre(Vector poblaciones) {
        Random r = new Random();
        int individuo1;
        int individuo2;
        int padre;
        int sorteo;
        int limite = poblaciones.size();
        //Obtenemos 2 numeros que vienen a ser los indices de los padres para llevar a cabo el torneo
        individuo1 = r.nextInt(limite);
        individuo2 = r.nextInt(limite);
        //Hacemos que los padres sean diferentes.
        while (individuo1 == individuo2) {
            individuo2 = r.nextInt(limite);
        }
        //Quitamos ambos individuos del parametro de entrada poblaciones.
        Individuo opcion1 = (Individuo) poblaciones.get(individuo1);
        Individuo opcion2 = (Individuo) poblaciones.get(individuo2);
        //Seleccionamos el individuo de mayor fitness.
        if (opcion1.getFitness() > opcion2.getFitness()) {
            padre = individuo1;
        } else if (opcion1.getFitness() < opcion2.getFitness()) {
            padre = individuo2;
            //Si los fitness son iguales realizamos un sorteo.
        } else {
            sorteo = r.nextInt(2);
            if (sorteo == 0) {
                padre = individuo1;
            } else {
                padre = individuo2;
            }
        }
        return padre;
    }
    
    /**
     *
     * Metodo utilizado para unir la Poblacion Actual y la Poblacion de No Dominados.
     * @return La union de ambas poblaciones.
     *
     */
    public Vector unirPoblaciones() {
        //Vector utilizado para guardar la union de las poblaciones.
        Vector poblacion = new Vector();
        int limite = 0;
        int indice = 0;
        Random r = new Random();
        //Ciclo utilizado para recorrer la Poblacion Actual.
        for (int i = 0; i < this.cantidadActual; i++) {
            //Agregamos el individuo de la Poblacion Actual al vector de union.
            poblacion.add(this.PA[i]);
        }
        limite = poblacion.size();
        //Ciclo para recorrer la Poblacion de No Dominados.
        for (int i = 0; i < this.PnD.size(); i++) {
            //Indice utilizado para ingresar a los individuos no dominados en lugares aleatorios.
            indice = r.nextInt(limite);
            //Agregamos el individuo de la Poblacion Actual al vector de union.
            poblacion.add(indice, this.PnD.get(i));
        }
        //Retornamos la union de ambas poblaciones.
        return poblacion;
    }
    
    /**
     *
     * Metodo utilizado para obtener el resultado final del algoritmo. Imprime los individuos con
     * sus cromosomas y los valores de su vector de objetivos de la Poblacion de No Dominados.
     *
     */
    public void resultado() {
        Individuo individuo;
        //Ciclo para recorrer la Poblacion de No Dominados.
        for (int i = 0; i < this.PnD.size(); i++) {
            //Quitamos un individuo de la poblacion.
            individuo = (Individuo) this.PnD.elementAt(i);
            //Imprimimos su cromosoma y valores de su vector de objetivos.
            System.out.println("Individuo " + (i + 1) + " = "  + " " + individuo.toStringVecObjetivo());
        }
    }
    
    /**
     *
     * Metodo utilizado para generar la nueva poblacion que reemplazara a la Poblacion Actual. Es
     * decir este metodo realiza tanto la seleccion de los padres a ser cruzados, si estos de cruzan o no,
     *  y si los hijos se mutan o no.
     * @param poblaciones Contiene todos los individuos de ambas poblaciones.
     *
     */
    public void seleccionYevolucionSPEA(Vector poblaciones) {
        Individuo padre1;
        Individuo padre2;
        int p1;
        int p2;
        Random r = new Random();
        //Creamos una nueva poblacion que reemplazara a la actual.
        Individuo[] nuevaPob = new Individuo[this.PA.length];
        Individuo[] aux;        
        //Ciclo para recorre la nueva poblacion.
        for (int i = 0; i < nuevaPob.length; i = i + 2) {
            //Seleccionamos los padres para el cruce.
            p1 = this.seleccionarPadre(poblaciones);
            p2 = this.seleccionarPadre(poblaciones);
            //Si los padres son iguales se realiza otra seleccion.
            while (p1 == p2) {
                p2 = this.seleccionarPadre(poblaciones);
            }
            //Obtenemos los individuos que son padres.
            padre1 = (Individuo) poblaciones.get(p1);
            padre2 = (Individuo) poblaciones.get(p2);
            //Preguntamos si se cruzan.
            if (r.nextDouble() <= this.pc) {
                aux = padre1.cruzar(padre2);
                //Preguntamos si el primer hijo se muta.
                if (r.nextDouble() > this.pm) {
                   aux[0].mutar();                   
                }
                //Preguntamos si el segundo hijo se muta.
                if (r.nextDouble() <= this.pm) {
                    aux[1].mutar();
                }
                //Se añaden los hijos a la nueva poblacion.
                nuevaPob[i] = aux[0];
                nuevaPob[i + 1] = aux[1];
            } else {
                //Si lo padres no se cruzan, los mismos se añaden a la nueva poblacion.
                nuevaPob[i] = padre1;
                nuevaPob[i + 1] = padre2;
            }
        }
        //La nueva poblacion reemplaza a la poblacion actual.
        this.PA = nuevaPob;
        //Se guarda la nueva cantidad de individuos de la poblacion actual.
        this.cantidadActual = nuevaPob.length;
    }
    
    /**
     * Realiza el metodo de clustering definido en el SPEA.
     */
    public void clusteringPnD(){
        this.clusters = new int [this.PnD.size()];
        this.listSgteClusters = new int [this.PnD.size()];
        this.numClusters = this.PnD.size();
        double minDistancia = Integer.MAX_VALUE;
        double distancia = 0.0;
        int indice1 = 0; 
        int indice2 = 0;
        
        //Inicialmente cada individuo de la Poblacion de no Dominados es un cluster distinto.
        for (int i = 0; i < this.PnD.size(); i++) {
            this.clusters[i] = i;
            this.listSgteClusters[i] = -1;
        }
        
        //Ahora se inicia el ciclo de reduccion de PnD, en cada paso se reduce el numero de cluster en 1.
        while(this.numClusters > this.maxTamanhoPnD){
            //Obtenemos los pares de clusters con distancia minima.
            
            for (int i = 0; i < this.numClusters; i++) {
                for (int j = i + 1; j < this.numClusters; j++) {                    
                        distancia = this.distanciaCluster(i, j);
                        if(distancia < minDistancia){
                            minDistancia = distancia;
                            indice1 = i;
                            indice2 = j;
                        }                
                }                
            }
            //Unimos los clusters con distancia minima.
            this.unirClusters(indice1, indice2);
        }
        //Creamos un PnD auxiliar para obtener la nueva poblacion luego del clustering. En esta variable auxiliar
        //iran los centroides de cada cluster.
        Vector auxPnD = new Vector();
        int auxIndi = 0;        
        for (int i = 0; i < this.numClusters; i++) {
            auxIndi = this.obtenerCentroide(i);
            auxPnD.add((Individuo)this.PnD.get(auxIndi));            
        }
        //Actualizamos el PnD y eliminamos el auxPnD.
        this.PnD = auxPnD;
        auxPnD = null;
    }
        
    /**
     * Calcula la distancia existente entre un par de clusters. La distancia es igual al promedio de distancia
     * entre los pares de individuos de los clusters.
     * @param c1 Contiene los individuos del primer cluster.
     * @param c2 Contiene los individuos del segundo cluster.
     * @return
     */
    public double distanciaCluster(int cluster1, int cluster2){
        double suma = 0.0;        
        int numPares = 0;
        int c2 = 0;
        int c1 = this.clusters[cluster1];
        
        while(c1 >= 0){
            c2 = this.clusters[cluster2];
            while(c2 >= 0){
                this.distancia((Individuo)this.PnD.get(c1), (Individuo)this.PnD.get(c2)); 
                numPares++;
                c2 = this.listSgteClusters[c2];
            }
            c1 = this.listSgteClusters[c1];
        }        
        return (suma/(double)numPares);
    }
    
    /**
     * Realiza la union de individuos de dos clusters, los individuos del segundo cluster pasan al primer cluster, luego el
     * segundo cluster es vaciado.
     * @param c1 Primer cluster.
     * @param c2 Segundo cluster.
     */
    public void unirClusters(int cluster1, int cluster2){
        int c1 = this.clusters[cluster1];
        while(this.listSgteClusters[c1] >= 0){
            c1 = this.listSgteClusters[c1];
        }
        
        this.listSgteClusters[c1] = this.clusters[cluster2];
        
        this.numClusters--;
        
        this.clusters[cluster2] = this.clusters[this.numClusters];
    }
    
    /**
     * Obtiene el centroide de un cluster, es decir el individuo con distancia minima a todos los demas 
     * individuos del cluster.
     * @param cluster Conjunto de individuos.
     * @return
     */
    public int obtenerCentroide(int cluster){
                
        int c1,c2,centroide = 0;
        double minSuma = Integer.MAX_VALUE;
        double suma = 0.0;
        c1 = this.clusters[cluster];
        while(c1 >= 0){
            c2 = this.clusters[cluster];
            while(c2 >= 0){
                suma += this.distancia((Individuo)this.PnD.get(c1), (Individuo)this.PnD.get(c2)); 
                c2 = this.listSgteClusters[c2];
            }
            if(suma < minSuma){
                minSuma = suma;
                centroide = c1;
            }
            c1 = this.listSgteClusters[c1];
        }
        return centroide;        
    }
    
    /**
     * Metodo para calcular la distancia de los objetivos entre 2 individuos.
     * @param i1 Individuo 1
     * @param i2 Individuo 2
     * @return
     */
    public double distancia (Individuo i1, Individuo i2){
        double suma = 0.0;
        int limite = i1.getVec_objetivo().length;
        for (int i = 0; i < limite; i++) {
            suma += Math.pow(i2.getValorObjetivo(i)-i1.getValorObjetivo(i), 2);            
        }
        return (Math.sqrt(suma));
        
    }
    
    /**
     * Realiza un test para saber si se excedio el limite de individuos en PnD.
     * @return
     */
    public boolean sePasoElLimite(){
        if(this.PnD.size() > this.maxTamanhoPnD){
            return true;
        }
        return false;
    }
} // Final de la Clase Poblacion